package com.example.algorithm.linked_list;

// 本案例演示的：合并两个排序的链表，merge方法的参数是两个链表的头节点，返回值是合成后的新链表的头结点。

// 对比学习：这个例子可以和 MergeSort 类中的那个例子，对比一起学习来看。两者有共通之处。
public class MergeSortedLinkedListSolution {

    // 示例
    public static void main(String[] args) {
        // 创建链表1：1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // 创建链表2：2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        // 合并两个链表并打印结果
        // 最后实际打印的结果为：1 -> 2 -> 3 -> 5 -> 6 -> 7 -> null。符合要求。
        ListNode mergedList = merge(l1, l2);  // mergedList不是一个列表哦，事实上，它是一个节点。
        while (mergedList != null) {
            System.out.print(mergedList.val + " -> ");
            mergedList = mergedList.next;
        }
        System.out.println("null");


        // 创建链表1：1 -> 2 -> 3
        ListNode l3 = new ListNode(1);
        l3.next = new ListNode(2);
        l3.next.next = new ListNode(3);

        // 创建链表2：5 -> 6 -> 7
        ListNode l4 = new ListNode(5);
        l4.next = new ListNode(6);
        l4.next.next = new ListNode(7);

        // 合并两个链表并打印结果
        // 最后实际打印的结果为：。符合要求。
        ListNode mergedList02 = merge(l3, l4);
        while (mergedList02 != null) {
            System.out.print(mergedList02.val + " -> ");
            mergedList02 = mergedList02.next;
        }
        System.out.println("null");

    }


    public static ListNode merge(ListNode l1, ListNode l2) {  // merge方法的参数是两个链表的头节点。循着l1、l2可以摸遍整条链表，所以，l1、l2既是节点，同时它们又代表了整条链表。

        // 创建一个dummy节点，方便处理头节点
        // 以下逻辑不在while循环体里面。说明以下逻辑仅仅只走一遍。单存的初始化逻辑而已。
        ListNode dummy = new ListNode(-1); //dummy,加的，虚拟的。本处表示它是一个虚拟的节点。
        ListNode current = dummy; // 这个节点相当于是给合并后的那个链表牵个头的。这样处理逻辑会简单一点。

        // 比较l1和l2当前节点的值，将小的节点接到current后面
        // 这个过程看懂了。
        // 这个while循环什么时候结束呢？当有一个单链表被率先遍历续接完的时候，那么while就结束了。那可能另一个链表还没有被遍历完，那怎么办？下方最后写了一个if else if来补上。
        while (l1 != null && l2 != null) { // l1和l2各自是自己所在排过序链表的最小元素。现在只要比较l1和l2的大小就行。
            if (l1.val < l2.val) { // 第一轮：l1=1 和 l2=2
                current.next = l1; // current现在代表的就是合并后的链表。给current续接上一个。
                l1 = l1.next; // l1被current.next使用之后，重新构造一个l1与上一轮没有被使用的l2比较。这个新l1就是当前l1的下一个元素。
            } else {
                current.next = l2; // 确定合并后的列表的下一个。第二轮：current.next = 2
                l2 = l2.next;  // l2被current.next使用之后，重新构造一个l2与上一轮没有被使用的l1比较。这个新l2就是当前l2的下一个元素。
            }
            // 第一轮：current = 1
            current = current.next; // 用完current之后。可以想象成就移动current指针。也就是再从某个链表里面取一个元素进来比而已。
        }

        // 将剩余的节点接到current后面
        // 这下面这一段，发觉看不懂。循环结束之后，是干嘛。
        // 慢慢的看懂了。很有可能，两个链表的大小差异非常大，然后，l1非常早的就遍历到null了，或者l2非常早的就遍历到null。那么，会有一个链表里面遗留比较多的节点。
        // 那么，这些所有的节点，只要把剩余节点的第一个节点和current接起来就好了。因为剩余节点之间它们本来就是按大小排好，并且链着的。
        if (l1 != null) {
            current.next = l1;
        } else if (l2 != null) {
            current.next = l2;
        }

        // 返回合并后的链表，从dummy.next开始是因为dummy是辅助节点
        return dummy.next; // 返回值是合成后的新链表的头结点
    }
}







